Counting Haybales (Binary Search)

Source: USACO 2016 December Contest (Silver) "Counting Haybales"

Tags: Binary Search, Easy

Data Structures used: Set

Problem

Solved on: Nov 6 2022

Time taken to solve: 1 hr 34 min

Problem Statement:

Farmer John has just arranged his N haybales (1 <= N <= 100,000) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer Q queries (1 <= Q <= 100,000), each asking for the number of haybales within a specific interval along the road

Input Format:

N Q
N distinct (space seperated) integers (0 - 1,000,000,000) that indicate there is a haybale at that location
[Q lines] - A and B (a<b<1,000,000,000) with queries for the number of haybales between A and B

Sample Input:

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

Sample Output:

2
2
3
4
1
0

Analysis:

There are N haybales and Q queries 
Each query asks how many haybales there are within a specific portion of the road
Brute force solution:
    - Create a bool array of N. Default value is 0 (false). Set a[n] to 1 if there is a haybale there. 

caution

The array size may be too large, and there may be too many operations

    - Create a set (std::set) because there will be no duplicate values. Store the value of N (the position of the haybale). Then, use set::find to find a and b. (Use std::distance(set.begin(), std::find(a)))

caution

Even though set is optimized, this does not run in time. Binary search is needed

Failed Solution (using sets) (time limit)

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

struct format{
    int a;
    int b;
};

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);

    set<int> data;
    data.insert(1000000001);
    int n, q;
    cin >> n >> q;

    format queries[q];

    for(int i=0; i<n; i++){
        int tempVar;
        cin >> tempVar;
        data.insert(tempVar);
    }


    for(int i=0; i<q; i++) {
        cin >> queries[i].a >> queries[i].b;

        auto aPos = data.find(queries[i].a);
        auto bPos = data.find(queries[i].b);

        bool deleteAPos = false;
        bool deleteBPos = false;
        if(aPos==data.end()){
            data.insert(queries[i].a);
            aPos = data.find(queries[i].a);
            deleteAPos = true;
        }
        if(bPos==data.end()){
            data.insert(queries[i].b);
            bPos = data.find(queries[i].b);
            deleteBPos = true;
        }

        int count=1;

        for (auto it = aPos; it != bPos; it++)
            count++;

        if(deleteAPos)
            count--;
        if(deleteBPos)
            count--;

        cout << count << '\n';

        if(deleteAPos)
            data.erase(aPos);

        if(deleteBPos)
            data.erase(bPos);
    }

    return 0;
}

Successful solution

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main (){
    int n, q;
    cin >> n >> q;

    vector<int> bales(n);
    for (int i = 0; i < n; i++) {
        cin >> bales[i];
    }

    sort(begin(bales), end(bales));
    for (int i = 0; i < q; i++) {
        int q_start;
        int q_end;
        cin >> q_start >> q_end;
        cout << upper_bound(begin(bales), end(bales), q_end) - lower_bound(begin(bales), end(bales), q_start) << "\n";
    }

    return 0;
}

See learn>C++>upper_bound & lower_bound for information on why this can be used

info

The numbers in the queries didnt have to be indexes where haybales existed, so the upper/lower_bound functions can finx the next one This is the same solution as the failed one, but slightly faster

tip

Think about all standard library functions avalible to you, they are usually the best optimized and can make it easier for you.